/**
 * 树的括号表示转换成树的孩子表示（数组方式）
 */
#include <stdio.h>
#include <stdlib.h>

#define m 3 // 树的度数
#define MAXSIZE 20
#define BMAXSIZE 50

typedef char datatype;
typedef struct node
{
    datatype data;
    int child[m];
} treenode;
treenode tree[MAXSIZE]; // 存储树的孩子表示法的数组
int root;               // 树的根结点的下标
int length;             // 树的结点数
char p[BMAXSIZE];       // 存储树的括号表示法的数组

/**
 * 将树的括号表示法转换成树的孩子表示法
 */
void brackettottree(char p[], int *root, int *length, treenode tree[])
{
    int stack[BMAXSIZE], top, i, j = 0, k = 0, l, done = 1;
    *root = 0;
    tree[j].data = p[k++];

    for (i = 0; i < m; ++i)
    {
        tree[j].child[i] = -1;
    }

    while (done)
    {
        if (p[k] == '(')
        {
            stack[top++] = j;
            ++k;
        }
        else if (p[k] == ')')
        {
            --top;
            if (top == 0)
                done = 0;
            else
                ++k;
        }
        else if (p[k] == ',')
        {
            ++k;
        }
        else
        {
            ++j;
            tree[j].data = p[k];

            for(i = 0; i < m; ++i)
            {
                tree[j].child[i] = -1;
            }

            l = stack[top - 1];
            i = 0;

            // 找到栈顶元素的第一个空孩子
            while (tree[l].child[i] != -1)
            {
                ++i;
            }

            tree[l].child[i] = j;
            ++k;
        }
    }

    *length = j + 1;
}


int main() {
    int i;
    char p[] = "A(B(D,E),C(F,G))";
    brackettottree(p, &root, &length, tree);
    printf("树的孩子表示法：\n");
    for (i = 0; i < length; ++i)
    {
        printf("%c: ", tree[i].data);
        for (int j = 0; j < m; ++j)
        {
            if (tree[i].child[j] != -1)
            {
                printf("%c ", tree[tree[i].child[j]].data);
            }
        }
        printf("\n");
    }
    return 0;
}